package gdut.edu.demo01;

import java.util.Arrays;

/**
 * @Description 数组的二分法查找，前提是数组必须是有序的，这里以升序的数组为例
 * @Author JiaFu
 * @Date 2022/7/6 15:13
 */
public class TestBinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
//        目标元素
        int target = 8;
//        目标元素所在的下标
        int index = -1;
//        起始位置
        int begin = 0;
//        结束位置
        int end = arr.length - 1;
//        中间位置
        int mid = (begin + end) / 2;
//        循环查找
        while (true) {
//            如果初始位置和结束位置重合或初始位置>结束位置，表示找不到该元素，跳出循环
            if (begin >= end) {
                break;
            }
//            如果找到目标元素，返回下标，停止查找
            if (arr[mid] == target) {
                index = mid;
                break;
//                如果中间元素不是要查找的元素
            } else {
//                判断中间元素是否比目标元素大
                if (arr[mid] > target) {
//                    调整结束位置为中间元素位置的前面一个位置
                    end = mid - 1;
//                    中间元素比目标元素小
                } else {
//                    调整起始位置为中间元素位置的下一个位置
                    begin = mid + 1;
                }
//                调整中间位置
                mid = (begin + end) / 2;
            }
        }

        System.out.println(Arrays.toString(arr));
        System.out.println("index = " + index);
    }
}
